#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <iterator>

using namespace std;
typedef map<int,vector<double> > BucketMap;
double SimapleArray[]={.79,.13,.16,.64,.39,.20,.89,.53,.71,.42};

void couting_sort(vector<double> &vecA)
{
	
	int k=vecA.size();
	vector<double> vecC;
	vector<double> vecB(k);
	for(int i=0;i<k+1;++i)
		vecC.push_back(0);
	for(int j=0;j<vecA.size();++j)
		++vecC[vecA[j]];
	for(int i=1;i<k+1;++i)
		vecC[i]=vecC[i]+vecC[i-1];
	for(int j=vecA.size()-1;j>=0;--j)
	{
		vecB[vecC[vecA[j]]-1]=vecA[j];
		--vecC[vecA[j]];
	}
	vecA=vecB;
}
void bucket_sort(vector<double> &vecA)
{
	BucketMap bucketmapB;
	int n=vecA.size();
	for(int i=0;i<n;++i)
	{
		bucketmapB.insert(make_pair(i,NULL));
	}
	for(int i=0;i<n;++i)
	{
		bucketmapB[floor(n*vecA[i])].push_back(vecA[i]);
	}
	vecA.clear();
	for(int i=0;i<n-1;++i)
	{
		if(bucketmapB.find(i)!=bucketmapB.end())
		{
			couting_sort(bucketmapB[i]);
			vecA.insert(vecA.end(),bucketmapB[i].begin(),bucketmapB[i].end());
		}
	}
		
}

int main()
{
	vector<double> A;

	
	int size=sizeof(SimapleArray)/sizeof(double);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
	cout << "Array before sorting\n";
	copy(A.begin(),A.end(),ostream_iterator<double>(cout," "));	
	cout<<endl;
	cout << "Bucket sorts the array"<<endl;
	bucket_sort(A);
	cout << "Array after sorting\n";
	copy(A.begin(),A.end(),ostream_iterator<double>(cout," "));
	cout<<endl;
	return 0;
}